package com.zhugang.week13.slidingwindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program algorithms
 * @description: findAnagrams
 * @author: chanzhugang
 * @create: 2022/09/19 17:31
 */
public class FindAnagrams {

    /**
     * 438 找到字符串中所有字母异位词
     * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        // s中找p的异位词，返回子串的起始位置：s中构建一个滑动窗口，大小和p长度一样

        // 异位词：把字符转成对应数组下标
        List<Integer> result = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        if (n > m) {
            return result;
        }

        int[] needs = new int[26];
        for (int i = 0; i < n; i++) {
            // 字符 映射 到数组下标， 统计字符出现的次数
            needs[p.charAt(i) - 'a']++;
        }

        int[] matched = new int[26];
        // 构建滑动窗口 大小和 p长度一样
        int start = 0;
        int end = 0;
        while (end < n) {
            matched[s.charAt(end) - 'a']++;
            end++;
        }
        if (same(matched, needs)) {
            // 找到一组解
            result.add(start);
        }
        // 窗口向右滑动
        while (start < m && end < m) {
            matched[s.charAt(start) - 'a']--;
            matched[s.charAt(end) - 'a']++;
            start++;
            end++;
            if (same(matched, needs)) {
                result.add(start);
            }
        }
        return result;
    }

    /**
     * 两个数组是否相等， 是否是异位词
     *
     * @param matched
     * @param needs
     * @return
     */
    private boolean same(int[] matched, int[] needs) {
        for (int i = 0; i < matched.length; i++) {
            if (matched[i] != needs[i]) {
                return false;
            }
        }
        return true;
    }

    // 推荐：滑动窗口，代码更简洁
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int m = s.length();
        int n = p.length();
        if (m < n) {
            return result;
        }

        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < n; i++) {
            // 字符映射到数组，值为字符的次数
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            result.add(0);
        }

        for (int i = 0; i < m - n; i++) {
            // 窗口向右滑动
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + n) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                result.add(i + 1);
            }
        }
        return result;
    }


}